﻿//using System;
//using System.Collections.Generic;
//using System.Linq;
//using System.Numerics;
//using System.Text;
//using ParserGenerator.Collections;
//using ParserGenerator.DataStructures;
//using ParserGenerator.Exceptions;
//using ParserGenerator.Extensions;
//using ParserGenerator.Input;
//using ParserGenerator.LexicalAnalysis;

//namespace ParserGenerator.Languages.Let
//{
//    partial class ProgramParser
//    {
//        private void ScanIdentifierValue()
//        {
//            string value = TokenContext.GetSource();
//            TokenValue = Name.New(value, TokenContext);
//        }

//        private void ScanNumberValue()
//        {
//            string str = TokenContext.GetSource();
//            TokenValue = BigInteger.Parse(str);
//        }
//    }

//    partial class Program
//    {
//        public Value Evaluate()
//        {
//            Environment env = new Environment();
//            env.Push("x", Value.NewNum(10));
//            env.Push("v", Value.NewNum(5));
//            env.Push("i", Value.NewNum(1));
//            ExpressionEvaluator evaluator = new ExpressionEvaluator(env);
//            Value value = evaluator.EvaluateExpression(Body);
//            return value;
//        }

//        public Type TypeCheck()
//        {
//            TypeEnvironment env = new TypeEnvironment();
//            env.Push("x", TypeChecker.IntType);
//            env.Push("v", TypeChecker.IntType);
//            env.Push("i", TypeChecker.IntType);
//            TypeChecker checker = new TypeChecker(env);
//            checker.CheckExpression(Body);
//            Type type = Body.Type;
//            return type;
//        }

//        public static void Test()
//        {
//            while (true)
//            {
//                SourceReader reader = SourceReader.FromConsole();
//                if (reader.Peek() == -1)
//                    break;
//                try
//                {
//                    ProgramParser parser = new ProgramParser(reader);
//                    Program ast = parser.Parse();
//                    Type type = ast.TypeCheck();
//                    Value value = ast.Evaluate();
//                    Console.WriteLine("{0} : {1}", value, type);
//                }
//                catch (Exception e)
//                {
//                    e.Print();
//                }
//            }
//        }
//    }

//    partial class Expression
//    {
//        public Type Type { get; set; }

//        public HashSet<string> GetFreeVariables()
//        {
//            return FreeVariableChecker.Instance.CheckExpression(this);
//        }
//    }

//    partial class Value
//    {
//        public sealed override string ToString()
//        {
//            if (IsNum)
//                return AsNum.Val.ToString();
//            else if (IsBool)
//                return AsBool.Val ? "true" : "false";
//            else if (IsPair || IsEmptyList)
//            {
//                StringBuilder sb = new StringBuilder();
//                sb.Append("(");
//                bool first = true;
//                Value n = this;
//                while (n.IsPair)
//                {
//                    if (first)
//                        first = false;
//                    else
//                        sb.Append(" ");
//                    sb.Append(n.AsPair.First);
//                    n = n.AsPair.Second;
//                }
//                if (!n.IsEmptyList)
//                {
//                    if (!first)
//                        sb.Append(" ");
//                    sb.Append(". ");
//                    sb.Append(n);
//                }
//                sb.Append(")");
//                return sb.ToString();
//            }
//            else if (IsProc)
//            {
//                return "#<procedure>";
//            }
//            else
//            {
//                return base.ToString();
//            }
//        }

//        public int ListLength()
//        {
//            if (IsPair || IsEmptyList)
//            {
//                int length = 0;
//                Value n = this;
//                while (n.IsPair)
//                {
//                    length++;
//                    n = n.AsPair.Second;
//                }
//                if (!n.IsEmptyList)
//                    return -1;
//                return length;
//            }
//            return -1;
//        }

//        public bool IsList() => ListLength() != -1;
//    }

//    [Serializable]
//    public sealed class Environment : SymbolStack<string, Value>
//    {
//    }

//    partial class Type
//    {
//        private Type _representative;

//        private Type FindRepresentative()
//        {
//            if (_representative != this)
//            {
//                if (_representative != null)
//                    _representative = _representative.FindRepresentative();
//                else
//                    _representative = this;
//            }
//            return _representative;
//        }

//        private void UnionWith(Type other)
//        {
//            if (other == null)
//                throw new ArgumentNullException(nameof(other));
//            Type x = FindRepresentative();
//            Type y = other.FindRepresentative();
//            if (y.IsTypeVar && !x.IsTypeVar)
//                y._representative = x;
//            else
//                x._representative = y;
//        }

//        private string ToStringImpl()
//        {
//            if (IsInt)
//                return "int";
//            else if (IsBool)
//                return "bool";
//            else if (IsTypeVar)
//            {
//                Type t = FindRepresentative();
//                if (t == this)
//                    return "?" + AsTypeVar.Number;
//                else
//                    return t.ToStringImpl();
//            }
//            else if (IsList)
//            {
//                return "[" + AsList.Element.ToStringImpl() + "]";
//            }
//            else if (IsFunc)
//            {
//                Func n = AsFunc;
//                StringBuilder sb = new StringBuilder();
//                for (int i = 0; i < n.Arguments.Count; i++)
//                {
//                    if (i > 0)
//                        sb.Append(" * ");
//                    Type arg = n.Arguments[i];
//                    if (arg.IsFunc)
//                        sb.AppendFormat("({0})", arg.ToStringImpl());
//                    else
//                        sb.Append(arg.ToStringImpl());
//                }
//                if (n.Arguments.Count == 0)
//                    sb.Append("()");
//                sb.Append(" -> ");
//                sb.Append(n.Result.ToStringImpl());
//                return sb.ToString();
//            }
//            else
//            {
//                throw new NotImplementedException();
//            }
//        }

//        public sealed override string ToString()
//        {
//            Type type = FindRepresentative();
//            return type.ToStringImpl();
//        }

//        public void UnifyWith(Type other)
//        {
//            if (other == null)
//                throw new ArgumentNullException(nameof(other));
//            Unify(this, other, null, null, ToString(), other.ToString());
//        }

//        public void UnifyWith(Type other, SourceContext context)
//        {
//            if (other == null)
//                throw new ArgumentNullException(nameof(other));
//            Unify(this, other, context, null, ToString(), other.ToString());
//        }

//        public void UnifyWith(Type other, SourceContext context1, SourceContext context2)
//        {
//            if (other == null)
//                throw new ArgumentNullException(nameof(other));
//            Unify(this, other, context1, context2, ToString(), other.ToString());
//        }

//        private static void Unify(Type type1, Type type2, SourceContext context1, SourceContext context2, string type1TopLevel, string type2TopLevel)
//        {
//            if (type1 == null)
//                throw new ArgumentNullException(nameof(type1));
//            if (type2 == null)
//                throw new ArgumentNullException(nameof(type2));
//            if (type1TopLevel == null)
//                throw new ArgumentNullException(nameof(type1TopLevel));
//            if (type2TopLevel == null)
//                throw new ArgumentNullException(nameof(type2TopLevel));
//            type1 = type1.FindRepresentative();
//            type2 = type2.FindRepresentative();
//            if (type1 == type2)
//                return;
//            else if (type1.IsInt && type2.IsInt)
//                return;
//            else if (type1.IsBool && type2.IsBool)
//                return;
//            else if (type1.IsTypeVar || type2.IsTypeVar)
//                type1.UnionWith(type2);
//            else if (type1.IsList && type2.IsList)
//            {
//                type1.UnionWith(type2);
//                Unify(type1.AsList.Element, type2.AsList.Element, context1, context2, type1TopLevel, type2TopLevel);
//            }
//            else if (type1.IsFunc && type2.IsFunc)
//            {
//                if (type1.AsFunc.Arguments.Count != type2.AsFunc.Arguments.Count)
//                {
//                    string message = string.Format(SR.CanNotUnifyFuncWithDifferentArgCount, type1TopLevel, type2TopLevel);
//                    TypeErrorException e = new TypeErrorException(message);
//                    e.AddLocation(context1);
//                    e.AddLocation(context2);
//                    throw e;
//                }
//                type1.UnionWith(type2);
//                Sequence<Type> args1 = type1.AsFunc.Arguments;
//                Sequence<Type> args2 = type2.AsFunc.Arguments;
//                for (int i = 0; i < args1.Count; i++)
//                    Unify(args1[i], args2[i], context1, context2, type1TopLevel, type2TopLevel);
//                Unify(type1.AsFunc.Result, type2.AsFunc.Result, context1, context2, type1TopLevel, type2TopLevel);
//            }
//            else
//            {
//                string message = string.Format(SR.CanNotUnifyTypes, type1TopLevel, type2TopLevel);
//                TypeErrorException e = new TypeErrorException(message);
//                e.AddLocation(context1);
//                e.AddLocation(context2);
//                throw e;
//            }
//        }
//    }

//    [Serializable]
//    public sealed class TypeEnvironment : SymbolStack<string, Type>
//    {
//    }

//    [Serializable]
//    internal sealed class FreeVariableChecker : IFreeVariableChecker
//    {
//        public static FreeVariableChecker Instance = new FreeVariableChecker();

//        public HashSet<string> CheckExpression(Expression n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return n.AcceptFreeVariableChecker(this);
//        }

//        public HashSet<string> CheckConstExpression(Expression.Const n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return new HashSet<string>();
//        }

//        public HashSet<string> CheckMinusExpression(Expression.Minus n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return CheckExpression(n.Operand);
//        }

//        public HashSet<string> CheckSumExpression(Expression.Sum n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> left = CheckExpression(n.Left);
//            HashSet<string> right = CheckExpression(n.Right);
//            left.UnionWith(right);
//            return left;
//        }

//        public HashSet<string> CheckDiffExpression(Expression.Diff n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> left = CheckExpression(n.Left);
//            HashSet<string> right = CheckExpression(n.Right);
//            left.UnionWith(right);
//            return left;
//        }

//        public HashSet<string> CheckProdExpression(Expression.Prod n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> left = CheckExpression(n.Left);
//            HashSet<string> right = CheckExpression(n.Right);
//            left.UnionWith(right);
//            return left;
//        }

//        public HashSet<string> CheckQuotExpression(Expression.Quot n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> left = CheckExpression(n.Left);
//            HashSet<string> right = CheckExpression(n.Right);
//            left.UnionWith(right);
//            return left;
//        }

//        public HashSet<string> CheckEqualExpression(Expression.Equal n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> left = CheckExpression(n.Left);
//            HashSet<string> right = CheckExpression(n.Right);
//            left.UnionWith(right);
//            return left;
//        }

//        public HashSet<string> CheckGreaterExpression(Expression.Greater n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> left = CheckExpression(n.Left);
//            HashSet<string> right = CheckExpression(n.Right);
//            left.UnionWith(right);
//            return left;
//        }

//        public HashSet<string> CheckLessExpression(Expression.Less n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> left = CheckExpression(n.Left);
//            HashSet<string> right = CheckExpression(n.Right);
//            left.UnionWith(right);
//            return left;
//        }

//        public HashSet<string> CheckIsZeroExpression(Expression.IsZero n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return CheckExpression(n.Operand);
//        }

//        public HashSet<string> CheckConsExpression(Expression.Cons n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> left = CheckExpression(n.Left);
//            HashSet<string> right = CheckExpression(n.Right);
//            left.UnionWith(right);
//            return left;
//        }

//        public HashSet<string> CheckCarExpression(Expression.Car n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return CheckExpression(n.Operand);
//        }

//        public HashSet<string> CheckCdrExpression(Expression.Cdr n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return CheckExpression(n.Operand);
//        }

//        public HashSet<string> CheckIsNullExpression(Expression.IsNull n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return CheckExpression(n.Operand);
//        }

//        public HashSet<string> CheckEmptyListExpression(Expression.EmptyList n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return new HashSet<string>();
//        }

//        public HashSet<string> CheckListExpression(Expression.List n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> set = new HashSet<string>();
//            foreach (Expression item in n.Elements)
//            {
//                HashSet<string> set2 = CheckExpression(item);
//                set.UnionWith(set2);
//            }
//            return set;
//        }

//        public HashSet<string> CheckTrueExpression(Expression.True n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return new HashSet<string>();
//        }

//        public HashSet<string> CheckFalseExpression(Expression.False n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return new HashSet<string>();
//        }

//        public HashSet<string> CheckIfExpression(Expression.If n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> set = CheckExpression(n.Test);
//            HashSet<string> set2 = CheckExpression(n.Body);
//            HashSet<string> set3 = CheckExpression(n.OrElse);
//            set.UnionWith(set2);
//            set.UnionWith(set3);
//            return set;
//        }

//        public HashSet<string> CheckCondExpression(Expression.Cond n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> set = new HashSet<string>();
//            foreach (ConditionActionPair pair in n.Branches)
//            {
//                HashSet<string> set2 = CheckExpression(pair.Condition);
//                HashSet<string> set3 = CheckExpression(pair.Action);
//                set.UnionWith(set2);
//                set.UnionWith(set3);
//            }
//            return set;
//        }

//        public HashSet<string> CheckPrintExpression(Expression.Print n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return CheckExpression(n.Operand);
//        }

//        public HashSet<string> CheckVarExpression(Expression.Var n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> set = new HashSet<string>();
//            set.Add(n.Name.Value);
//            return set;
//        }

//        public HashSet<string> CheckLetExpression(Expression.Let n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> set = new HashSet<string>();
//            for (int j = 0; j < n.Bindings.Count; j++)
//            {
//                HashSet<string> set2 = CheckExpression(n.Bindings[j].Value);
//                if (n.IsSequential)
//                    for (int i = 0; i < j; i++)
//                        set2.Remove(n.Bindings[i].Name.Value);
//                set.UnionWith(set2);
//            }
//            HashSet<string> set3 = CheckExpression(n.Body);
//            foreach (NameValuePair pair in n.Bindings)
//                set3.Remove(pair.Name.Value);
//            set.UnionWith(set3);
//            return set;
//        }

//        public HashSet<string> CheckLetrecExpression(Expression.Letrec n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> set = new HashSet<string>();
//            foreach (LetrecProcedure procedure in n.Procedures)
//            {
//                HashSet<string> set2 = CheckExpression(procedure.Body);
//                foreach (Parameter param in procedure.Parameters)
//                    set2.Remove(param.Name.Value);
//                foreach (LetrecProcedure p in n.Procedures)
//                    set2.Remove(p.Name.Value);
//                set.UnionWith(set2);
//            }
//            HashSet<string> set3 = CheckExpression(n.Body);
//            foreach (LetrecProcedure p in n.Procedures)
//                set3.Remove(p.Name.Value);
//            set.UnionWith(set3);
//            return set;
//        }

//        public HashSet<string> CheckUnpackExpression(Expression.Unpack n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> set = CheckExpression(n.Value);
//            HashSet<string> set2 = CheckExpression(n.Body);
//            foreach (Name name in n.Names)
//                set2.Remove(name.Value);
//            set.UnionWith(set2);
//            return set;
//        }

//        public HashSet<string> CheckCallExpression(Expression.Call n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> set = CheckExpression(n.Operator);
//            foreach (Expression operand in n.Operands)
//            {
//                HashSet<string> set2 = CheckExpression(operand);
//                set.UnionWith(set2);
//            }
//            return set;
//        }

//        public HashSet<string> CheckProcExpression(Expression.Proc n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            HashSet<string> set = CheckExpression(n.Body);
//            foreach (Parameter param in n.Parameters)
//                set.Remove(param.Name.Value);
//            return set;
//        }
//    }

//    [Serializable]
//    internal sealed class ExpressionEvaluator : IExpressionEvaluator
//    {
//        private Environment _env;

//        public ExpressionEvaluator(Environment env)
//        {
//            if (env == null)
//                throw new ArgumentNullException(nameof(env));
//            _env = env;
//        }

//        public Value EvaluateExpression(Expression n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return n.AcceptExpressionEvaluator(this);
//        }

//        public Value EvaluateConstExpression(Expression.Const n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return Value.NewNum(n.Value);
//        }

//        public Value EvaluateMinusExpression(Expression.Minus n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value val = EvaluateExpression(n.Operand);
//            Value result = Value.NewNum(-val.AsNum.Val);
//            return result;
//        }

//        public Value EvaluateSumExpression(Expression.Sum n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value left = EvaluateExpression(n.Left);
//            Value right = EvaluateExpression(n.Right);
//            Value result = Value.NewNum(left.AsNum.Val + right.AsNum.Val);
//            return result;
//        }

//        public Value EvaluateDiffExpression(Expression.Diff n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value left = EvaluateExpression(n.Left);
//            Value right = EvaluateExpression(n.Right);
//            Value result = Value.NewNum(left.AsNum.Val - right.AsNum.Val);
//            return result;
//        }

//        public Value EvaluateProdExpression(Expression.Prod n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value left = EvaluateExpression(n.Left);
//            Value right = EvaluateExpression(n.Right);
//            Value result = Value.NewNum(left.AsNum.Val * right.AsNum.Val);
//            return result;
//        }

//        public Value EvaluateQuotExpression(Expression.Quot n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value left = EvaluateExpression(n.Left);
//            Value right = EvaluateExpression(n.Right);
//            Value result = Value.NewNum(left.AsNum.Val / right.AsNum.Val);
//            return result;
//        }

//        public Value EvaluateEqualExpression(Expression.Equal n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value left = EvaluateExpression(n.Left);
//            Value right = EvaluateExpression(n.Right);
//            Value result = Value.NewBool(left.AsNum.Val == right.AsNum.Val);
//            return result;
//        }

//        public Value EvaluateGreaterExpression(Expression.Greater n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value left = EvaluateExpression(n.Left);
//            Value right = EvaluateExpression(n.Right);
//            Value result = Value.NewBool(left.AsNum.Val > right.AsNum.Val);
//            return result;
//        }

//        public Value EvaluateLessExpression(Expression.Less n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value left = EvaluateExpression(n.Left);
//            Value right = EvaluateExpression(n.Right);
//            Value result = Value.NewBool(left.AsNum.Val < right.AsNum.Val);
//            return result;
//        }

//        public Value EvaluateIsZeroExpression(Expression.IsZero n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value val = EvaluateExpression(n.Operand);
//            Value result = Value.NewBool(val.AsNum.Val.IsZero);
//            return result;
//        }

//        public Value EvaluateConsExpression(Expression.Cons n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value left = EvaluateExpression(n.Left);
//            Value right = EvaluateExpression(n.Right);
//            Value result = Value.NewPair(left, right);
//            return result;
//        }

//        public Value EvaluateCarExpression(Expression.Car n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value val = EvaluateExpression(n.Operand);
//            Value result = val.AsPair.First;
//            return result;
//        }

//        public Value EvaluateCdrExpression(Expression.Cdr n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value val = EvaluateExpression(n.Operand);
//            Value result = val.AsPair.Second;
//            return result;
//        }

//        public Value EvaluateIsNullExpression(Expression.IsNull n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value val = EvaluateExpression(n.Operand);
//            Value result = Value.NewBool(val.IsEmptyList);
//            return result;
//        }

//        public Value EvaluateEmptyListExpression(Expression.EmptyList n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return Value.NewEmptyList();
//        }

//        public Value EvaluateListExpression(Expression.List n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            List<Value> list = new List<Value>();
//            foreach (Expression item in n.Elements)
//            {
//                Value val = EvaluateExpression(item);
//                list.Add(val);
//            }
//            Value result = Value.NewEmptyList();
//            for (int i = list.Count - 1; i >= 0; i--)
//                result = Value.NewPair(list[i], result);
//            return result;
//        }

//        public Value EvaluateTrueExpression(Expression.True n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return Value.NewBool(true);
//        }

//        public Value EvaluateFalseExpression(Expression.False n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            return Value.NewBool(false);
//        }

//        public Value EvaluateIfExpression(Expression.If n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value cond = EvaluateExpression(n.Test);
//            if (cond.AsBool.Val)
//                return EvaluateExpression(n.Body);
//            else
//                return EvaluateExpression(n.OrElse);
//        }

//        public Value EvaluateCondExpression(Expression.Cond n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            foreach (ConditionActionPair pair in n.Branches)
//            {
//                Value val = EvaluateExpression(pair.Condition);
//                if (val.AsBool.Val)
//                {
//                    Value result = EvaluateExpression(pair.Action);
//                    return result;
//                }
//            }
//            RuntimeErrorException e = new RuntimeErrorException(SR.CondBranchesExhausted);
//            e.AddLocation(n.Context);
//            throw e;
//        }

//        public Value EvaluatePrintExpression(Expression.Print n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value val = EvaluateExpression(n.Operand);
//            Console.WriteLine(val);
//            return Value.NewNum(1);
//        }

//        public Value EvaluateVarExpression(Expression.Var n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value result = _env.FindValue(n.Name.Value, n.Name.Context);
//            return result;
//        }

//        public Value EvaluateLetExpression(Expression.Let n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            if (n.IsSequential)
//            {
//                foreach (NameValuePair pair in n.Bindings)
//                {
//                    Value value = EvaluateExpression(pair.Value);
//                    _env.Push(pair.Name.Value, value);
//                }
//            }
//            else
//            {
//                List<Value> values = new List<Value>(n.Bindings.Count);
//                foreach (NameValuePair pair in n.Bindings)
//                {
//                    Value value = EvaluateExpression(pair.Value);
//                    values.Add(value);
//                }
//                for (int i = 0; i < n.Bindings.Count; i++)
//                    _env.Push(n.Bindings[i].Name.Value, values[i]);
//            }
//            Value result = EvaluateExpression(n.Body);
//            _env.Pop(n.Bindings.Count);
//            return result;
//        }

//        public Value EvaluateLetrecExpression(Expression.Letrec n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            List<Value> procs = new List<Value>(n.Procedures.Count);
//            foreach (LetrecProcedure procedure in n.Procedures)
//            {
//                Sequence<Name> parameters = Sequence.New(from x in procedure.Parameters select x.Name);
//                Value proc = Value.NewProc(parameters, procedure.Body, new Environment());
//                procs.Add(proc);
//                _env.Push(procedure.Name.Value, proc);
//            }
//            foreach (Value proc in procs)
//            {
//                HashSet<string> fvs = proc.AsProc.Body.GetFreeVariables();
//                foreach (Name name in proc.AsProc.Parameters)
//                    fvs.Remove(name.Value);
//                foreach (string fv in fvs)
//                {
//                    Value value = _env.LookupValue(fv);
//                    proc.AsProc.Env.Push(fv, value);
//                }
//            }
//            Value result = EvaluateExpression(n.Body);
//            _env.Pop(n.Procedures.Count);
//            return result;
//        }

//        public Value EvaluateUnpackExpression(Expression.Unpack n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Value value = EvaluateExpression(n.Value);
//            int length = value.ListLength();
//            if (length == -1)
//            {
//                TypeErrorException e = new TypeErrorException(SR.ValueNotList);
//                e.AddLocation(n.Value.Context);
//                throw e;
//            }
//            if (length != n.Names.Count)
//            {
//                RuntimeErrorException e = new RuntimeErrorException(SR.ListLengthMismatch);
//                e.AddLocation(n.Value.Context);
//                throw e;
//            }
//            int index = 0;
//            for (Value v = value; v.IsPair; v = v.AsPair.Second)
//                _env.Push(n.Names[index++].Value, v.AsPair.First);
//            Value result = EvaluateExpression(n.Body);
//            _env.Pop(n.Names.Count);
//            return result;
//        }

//        public Value EvaluateProcExpression(Expression.Proc n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Sequence<Name> parameters = Sequence.New(from x in n.Parameters select x.Name);
//            HashSet<string> fvs = n.GetFreeVariables();
//            Environment env = new Environment();
//            foreach (string fv in fvs)
//            {
//                Value value = _env.LookupValue(fv);
//                env.Push(fv, value);
//            }
//            Value result = Value.NewProc(parameters, n.Body, env);
//            return result;
//        }

//        public Value EvaluateCallExpression(Expression.Call n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            List<Value> args = new List<Value>();
//            Value op = EvaluateExpression(n.Operator);
//            foreach (Expression operand in n.Operands)
//            {
//                Value arg = EvaluateExpression(operand);
//                args.Add(arg);
//            }
//            if (args.Count != op.AsProc.Parameters.Count)
//            {
//                RuntimeErrorException e = new RuntimeErrorException(SR.ArgumentCountMismatch);
//                e.AddLocation(n.Operator.Context);
//                throw e;
//            }
//            Environment savedEnv = _env;
//            _env = op.AsProc.Env;
//            int index = 0;
//            foreach (Value arg in args)
//                _env.Push(op.AsProc.Parameters[index++].Value, arg);
//            Value result = EvaluateExpression(op.AsProc.Body);
//            _env.Pop(args.Count);
//            _env = savedEnv;
//            return result;
//        }
//    }

//    [Serializable]
//    internal sealed class TypeChecker : ITypeChecker
//    {
//        public static Type IntType = Type.NewInt();
//        public static Type BoolType = Type.NewBool();

//        private TypeEnvironment _env;
//        private int _typeVarNumber;

//        public TypeChecker(TypeEnvironment env)
//        {
//            if (env == null)
//                throw new ArgumentNullException(nameof(env));
//            _env = env;
//        }

//        private Type GetFreshTypeVariable()
//        {
//            return Type.NewTypeVar(++_typeVarNumber);
//        }

//        private void CheckDuplicateNames(IEnumerable<Name> names)
//        {
//            if (names == null)
//                throw new ArgumentNullException(nameof(names));
//            var dict = new Dictionary<string, Name>();
//            foreach (Name name in names)
//            {
//                Name n;
//                if (dict.TryGetValue(name.Value, out n))
//                {
//                    NameErrorException e = new NameErrorException(SR.DuplicateNamesInBindingList);
//                    e.AddLocation(n.Context);
//                    e.AddLocation(name.Context);
//                    throw e;
//                }
//                dict.Add(name.Value, name);
//            }
//        }

//        public void CheckExpression(Expression n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            n.AcceptTypeChecker(this);
//        }

//        public void CheckConstExpression(Expression.Const n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            n.Type = IntType;
//        }

//        public void CheckMinusExpression(Expression.Minus n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Operand);
//            n.Operand.Type.UnifyWith(IntType, n.Operand.Context);
//            n.Type = IntType;
//        }

//        public void CheckSumExpression(Expression.Sum n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Left);
//            CheckExpression(n.Right);
//            n.Left.Type.UnifyWith(IntType, n.Left.Context);
//            n.Right.Type.UnifyWith(IntType, n.Right.Context);
//            n.Type = IntType;
//        }

//        public void CheckDiffExpression(Expression.Diff n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Left);
//            CheckExpression(n.Right);
//            n.Left.Type.UnifyWith(IntType, n.Left.Context);
//            n.Right.Type.UnifyWith(IntType, n.Right.Context);
//            n.Type = IntType;
//        }

//        public void CheckProdExpression(Expression.Prod n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Left);
//            CheckExpression(n.Right);
//            n.Left.Type.UnifyWith(IntType, n.Left.Context);
//            n.Right.Type.UnifyWith(IntType, n.Right.Context);
//            n.Type = IntType;
//        }

//        public void CheckQuotExpression(Expression.Quot n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Left);
//            CheckExpression(n.Right);
//            n.Left.Type.UnifyWith(IntType, n.Left.Context);
//            n.Right.Type.UnifyWith(IntType, n.Right.Context);
//            n.Type = IntType;
//        }

//        public void CheckEqualExpression(Expression.Equal n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Left);
//            CheckExpression(n.Right);
//            n.Left.Type.UnifyWith(IntType, n.Left.Context);
//            n.Right.Type.UnifyWith(IntType, n.Right.Context);
//            n.Type = BoolType;
//        }

//        public void CheckGreaterExpression(Expression.Greater n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Left);
//            CheckExpression(n.Right);
//            n.Left.Type.UnifyWith(IntType, n.Left.Context);
//            n.Right.Type.UnifyWith(IntType, n.Right.Context);
//            n.Type = BoolType;
//        }

//        public void CheckLessExpression(Expression.Less n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Left);
//            CheckExpression(n.Right);
//            n.Left.Type.UnifyWith(IntType, n.Left.Context);
//            n.Right.Type.UnifyWith(IntType, n.Right.Context);
//            n.Type = BoolType;
//        }

//        public void CheckIsZeroExpression(Expression.IsZero n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Operand);
//            n.Operand.Type.UnifyWith(IntType, n.Operand.Context);
//            n.Type = BoolType;
//        }

//        public void CheckConsExpression(Expression.Cons n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Left);
//            CheckExpression(n.Right);
//            Type listType = Type.NewList(n.Left.Type);
//            n.Right.Type.UnifyWith(listType, n.Right.Context);
//            n.Type = n.Right.Type;
//        }

//        public void CheckCarExpression(Expression.Car n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Operand);
//            Type elementType = GetFreshTypeVariable();
//            Type listType = Type.NewList(elementType);
//            n.Operand.Type.UnifyWith(listType, n.Operand.Context);
//            n.Type = elementType;
//        }

//        public void CheckCdrExpression(Expression.Cdr n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Operand);
//            Type elementType = GetFreshTypeVariable();
//            Type listType = Type.NewList(elementType);
//            n.Operand.Type.UnifyWith(listType, n.Operand.Context);
//            n.Type = n.Operand.Type;
//        }

//        public void CheckIsNullExpression(Expression.IsNull n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Operand);
//            Type elementType = GetFreshTypeVariable();
//            Type listType = Type.NewList(elementType);
//            n.Operand.Type.UnifyWith(listType, n.Operand.Context);
//            n.Type = BoolType;
//        }

//        public void CheckEmptyListExpression(Expression.EmptyList n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Type elementType = GetFreshTypeVariable();
//            Type listType = Type.NewList(elementType);
//            n.Type = listType;
//        }

//        public void CheckListExpression(Expression.List n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Type type = null;
//            SourceContext context = null;
//            foreach (Expression element in n.Elements)
//            {
//                CheckExpression(element);
//                if (type == null)
//                {
//                    type = element.Type;
//                    context = element.Context;
//                }
//                else
//                {
//                    type.UnifyWith(element.Type, context, element.Context);
//                }
//            }
//            n.Type = Type.NewList(type);
//        }

//        public void CheckTrueExpression(Expression.True n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            n.Type = BoolType;
//        }

//        public void CheckFalseExpression(Expression.False n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            n.Type = BoolType;
//        }

//        public void CheckIfExpression(Expression.If n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Test);
//            CheckExpression(n.Body);
//            CheckExpression(n.OrElse);
//            n.Test.Type.UnifyWith(BoolType, n.Test.Context);
//            n.Body.Type.UnifyWith(n.OrElse.Type, n.Body.Context, n.OrElse.Context);
//            n.Type = n.Body.Type;
//        }

//        public void CheckCondExpression(Expression.Cond n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Type type = null;
//            SourceContext context = null;
//            foreach (ConditionActionPair pair in n.Branches)
//            {
//                CheckExpression(pair.Condition);
//                pair.Condition.Type.UnifyWith(BoolType, pair.Condition.Context);
//                CheckExpression(pair.Action);
//                if (type == null)
//                {
//                    type = pair.Action.Type;
//                    context = pair.Action.Context;
//                }
//                else
//                {
//                    type.UnifyWith(pair.Action.Type, context, pair.Action.Context);
//                }
//            }
//            n.Type = type;
//        }

//        public void CheckPrintExpression(Expression.Print n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Operand);
//            n.Type = IntType;
//        }

//        public void CheckVarExpression(Expression.Var n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            n.Type = _env.FindValue(n.Name.Value, n.Name.Context);
//        }

//        public void CheckLetExpression(Expression.Let n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            if (!n.IsSequential)
//                CheckDuplicateNames(from x in n.Bindings select x.Name);
//            if (n.IsSequential)
//            {
//                foreach (NameValuePair pair in n.Bindings)
//                {
//                    CheckExpression(pair.Value);
//                    _env.Push(pair.Name.Value, pair.Value.Type);
//                }
//            }
//            else
//            {
//                foreach (NameValuePair pair in n.Bindings)
//                    CheckExpression(pair.Value);
//                foreach (NameValuePair pair in n.Bindings)
//                    _env.Push(pair.Name.Value, pair.Value.Type);
//            }
//            CheckExpression(n.Body);
//            _env.Pop(n.Bindings.Count);
//            n.Type = n.Body.Type;
//        }

//        public void CheckLetrecExpression(Expression.Letrec n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            var procNames = from x in n.Procedures select x.Name;
//            CheckDuplicateNames(procNames);
//            foreach (LetrecProcedure procedure in n.Procedures)
//            {
//                Sequence<Name> parameters = Sequence.New(from x in procedure.Parameters select x.Name);
//                CheckDuplicateNames(Enumerable.Concat(parameters, procNames));
//                foreach (Parameter param in procedure.Parameters)
//                    if (param.Type == null)
//                        param.Type = GetFreshTypeVariable();
//                if (procedure.ResultType == null)
//                    procedure.ResultType = GetFreshTypeVariable();
//                Sequence<Type> arguments = Sequence.New(from x in procedure.Parameters select x.Type);
//                Type type = Type.NewFunc(arguments, procedure.ResultType);
//                _env.Push(procedure.Name.Value, type);
//            }
//            foreach (LetrecProcedure procedure in n.Procedures)
//            {
//                foreach (Parameter param in procedure.Parameters)
//                    _env.Push(param.Name.Value, param.Type);
//                CheckExpression(procedure.Body);
//                _env.Pop(procedure.Parameters.Count);
//                procedure.Body.Type.UnifyWith(procedure.ResultType, procedure.Body.Context);
//            }
//            CheckExpression(n.Body);
//            _env.Pop(n.Procedures.Count);
//            n.Type = n.Body.Type;
//        }

//        public void CheckUnpackExpression(Expression.Unpack n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckDuplicateNames(n.Names);
//            CheckExpression(n.Value);
//            Type elementType = GetFreshTypeVariable();
//            Type listType = Type.NewList(elementType);
//            n.Value.Type.UnifyWith(listType, n.Value.Context);
//            foreach (Name name in n.Names)
//                _env.Push(name.Value, elementType);
//            CheckExpression(n.Body);
//            _env.Pop(n.Names.Count);
//            n.Type = n.Body.Type;
//        }

//        public void CheckProcExpression(Expression.Proc n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            Sequence<Name> parameters = Sequence.New(from x in n.Parameters select x.Name);
//            CheckDuplicateNames(parameters);
//            foreach (Parameter param in n.Parameters)
//                if (param.Type == null)
//                    param.Type = GetFreshTypeVariable();
//            foreach (Parameter param in n.Parameters)
//                _env.Push(param.Name.Value, param.Type);
//            CheckExpression(n.Body);
//            _env.Pop(n.Parameters.Count);
//            Sequence<Type> arguments = Sequence.New(from x in n.Parameters select x.Type);
//            n.Type = Type.NewFunc(arguments, n.Body.Type);
//        }

//        public void CheckCallExpression(Expression.Call n)
//        {
//            if (n == null)
//                throw new ArgumentNullException(nameof(n));
//            CheckExpression(n.Operator);
//            foreach (Expression operand in n.Operands)
//                CheckExpression(operand);
//            Sequence<Type> arguments = Sequence.New(from x in n.Operands select x.Type);
//            Type resultType = GetFreshTypeVariable();
//            Type funcType = Type.NewFunc(Sequence.New(arguments), resultType);
//            n.Operator.Type.UnifyWith(funcType, n.Operator.Context);
//            n.Type = resultType;
//        }
//    }
//}
